package com.company.sort;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] array = {3, 1, 2, 4, 56, 73, 54, 23, 42, 13, 345, 59};

        bubbleSort(array);
        // 打印排序结果
        System.out.println(Arrays.toString(array));

    }

    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] array) {
        if (null == array || array.length <= 1) {
            return;
        }

        int length = array.length;

        int num = 0;
        // 外层循环控制比较轮数i
        for (int i = 0; i < length; i++) {
            System.out.println("外层循环次数：" + (i + 1));
            boolean flag = true;
            // 内层循环控制每一轮比较次数，每进行一轮排序都会找出一个较大值
            // (array.length - 1)防止索引越界
            // (array.length - 1 - i)减少比较次数
            for (int j = 0; j < length - 1 - i; j++) {

                System.out.println("内层循环次数：" + (j + 1));
                // 前面的数大于后面的数就进行交换
                if (array[j] > array[j + 1]) {
                    flag = false;
                    System.out.println("交换次数：" + ++num);
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
            if (flag) {
                break;
            }
        }
    }

    /**
     * 选择排序
     */
    public static void selectionSort(int[] array) {
        if (null == array || array.length <= 1) {
            return;
        }

        int length = array.length;

        //外层循环
        for (int i = 0; i < length - 1; i++) {
            //最小值索引
            int minIndex = i;

            for (int j = i + 1; j < length; j++) {
                //匹配最小值
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }

            }

            //交换元素位置
            if (i != minIndex) {
                swap(array, minIndex, i);
            }

        }

    }

    /**
     * 交换元素位置
     */
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    /**
     * 插入排序
     * 通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
     */
    public static void insertionSort(int[] array) {
        if (null == array || array.length <= 1) {
            return;
        }

        int length = array.length;

        //要插入的数
        int insertNum;

        for (int i = 1; i < length; i++) {

            insertNum = array[i];
            // 已排序元素个数
            int j = i - 1;


            while (j >= 0 && array[j] > insertNum) {
                // 从后到前循环，将大于insertNum的数向后移动一格
                array[j + 1] = array[j];
                j--;
            }

            // 将需要插入的数放在要插入的位置
            array[j + 1] = insertNum;

        }
    }

}
